package vip.zhenzicheng.algorithm.sort;

import java.util.Arrays;

import static vip.zhenzicheng.algorithm.util.ArrayUtils.swap;

/**
 * 插入排序
 *
 * @author zhenzicheng
 * @date: 2022-05-17 08:52
 */
public class InsertSort {
  public static void main(String[] args) {
    int[] arr = {6, 2, 8, 9, 2, 0, 5, 7, 1, 26, 55, 11, 5, 9, 1, 3, 7, 3, 23, 48, 1, 34, 1};
    int[] arr2 = {6, 2, 8, 9, 2, 0, 5, 7, 1, 26, 55, 11, 5, 9, 1, 3, 7, 3, 23, 48, 1, 34, 1};

    // 普通插入排序
    insertSort1(arr);
    System.out.println(Arrays.toString(arr));
    // 优化插入排序
    insertSort2(arr2);
    System.out.println(Arrays.toString(arr2));
  }

  public static void insertSort1(int[] arr) {
    if (arr == null || arr.length < 2) {
      return;
    }
    int N = arr.length;
    for (int i = 1; i < N; i++) {
      int newNumIndex = i; // 相当于第二个数，所以往左看
      while (newNumIndex - 1 >= 0 && arr[newNumIndex - 1] > arr[newNumIndex]) {
        swap(arr, newNumIndex - 1, newNumIndex);
        newNumIndex--;
      }
    }
  }

  public static void insertSort2(int[] arr) {
    if (arr == null || arr.length < 2) {
      return;
    }
    int N = arr.length;
    for (int end = 1; end < N; end++) {
      for (int pre = end - 1; pre >= 0 && arr[pre] > arr[pre + 1]; pre--) {
        swap(arr, pre, pre + 1);
      }
    }
  }

}
